#ifndef DICCTRIE_H_
#define DICCTRIE_H_

#include "aed2.h"

using namespace aed2;
using namespace std;

template<typename T>
class DiccionarioTrie {

	private:

		struct Nodo{

			T* significado;
			Nodo* hojas[256];
			bool definido;

			Nodo();
		};

		Nodo* raiz;

		Lista<string> claves_;

	public:
		DiccionarioTrie();
		DiccionarioTrie(const DiccionarioTrie<T>& d);

		~DiccionarioTrie();
		void borrarTrie(Nodo*);

		void definir(string c, T& s);

		bool estaDefinido(string c);

		T* obtener(string c);
		void copiarTries(Nodo* n, Nodo* n2);
		bool operator==(const DiccionarioTrie<T>& d)const;
		bool NodosIguales(const Nodo* n1,const Nodo* n2)const;

		Lista<string>* claves();
};

template<typename T>
DiccionarioTrie<T>::DiccionarioTrie(){
	raiz = new Nodo();
};

template<typename T>
DiccionarioTrie<T>::Nodo::Nodo(){
	significado = NULL;
	definido = false;
	for(int i=0; i<256; i++)
		hojas[i]=NULL;
};

template<typename T>
DiccionarioTrie<T>::~DiccionarioTrie(){

	if(raiz!=NULL){
		int hoja = 0;
		Nodo* nodoAux = raiz;

		while(hoja<256){

			nodoAux = raiz->hojas[hoja];

			if(nodoAux!=NULL){

				borrarTrie(nodoAux);
				delete raiz->hojas[hoja];
			}
			hoja++;
		}
		delete raiz;
	}
};

template<typename T>
void DiccionarioTrie<T>::borrarTrie(Nodo* n){

	int hoja = 0;
	Nodo* nodoAux;

	while(hoja<256){

		nodoAux = n->hojas[hoja];

		if(nodoAux!=NULL){
			borrarTrie(nodoAux);
			delete nodoAux;
		}
		hoja++;
	}
}

template<typename T>
void DiccionarioTrie<T>::definir(string c, T& s){

	int i = 0;
	Nodo* nodoAux = raiz;
	while(c[i] != 0){

		int hoja = (int) c[i];

		if((nodoAux->hojas[hoja]) == NULL){
			nodoAux->hojas[hoja] = new Nodo();
		}

		nodoAux = nodoAux->hojas[hoja];
		i++;
	}
	nodoAux->significado = &s;
	nodoAux->definido = true;
	i++;

	claves_.AgregarAdelante(c);

};

template<typename T>
bool DiccionarioTrie<T>::estaDefinido(string c){

	int i = 0;
	Nodo* nodoAux = raiz;

	while((c[i]!=0)){

		char hoja = c[i];
		nodoAux = nodoAux->hojas[hoja];

		if(nodoAux == NULL)
			return false;

		i++;
	}
	return (nodoAux->definido);
};

template<typename T>
T* DiccionarioTrie<T>::obtener(string c){

	int i = 0;
	Nodo* nodoAux = raiz;

	while(c[i]!=0) {

		int hoja = (int) c[i];
		nodoAux =  nodoAux->hojas[hoja];

		i++;
	}
	return (nodoAux->significado);
};

template<typename T>
Lista<string>* DiccionarioTrie<T>::claves(){

    return &claves_;

};

template<typename T>
DiccionarioTrie<T>::DiccionarioTrie(const DiccionarioTrie<T>& d){

	raiz = new Nodo();
	int i=0;
	while(i<256){
		if((d.raiz->hojas[i])!=NULL){
			raiz->hojas[i] = new Nodo();
			copiarTries(raiz->hojas[i], d.raiz->hojas[i]);
		}
		i++;
	}
};

template<typename T>
void DiccionarioTrie<T>::copiarTries(Nodo* n, Nodo* n2){

	if(n2->definido)
		n->significado = n2->significado;

	n->definido = n2->definido;
	int i = 0;
	while(i<256){
		if(n2->hojas[i]!=NULL){
			n->hojas[i] = new Nodo();
			copiarTries(n->hojas[i], n2->hojas[i]);
		}
		i++;
	}
}

template<typename T>
bool DiccionarioTrie<T>::operator==(const DiccionarioTrie<T>& d)const{

	bool res = true;
	int i = 0;
	Nodo* n1 = raiz;
	Nodo* n2 = d.raiz;

	while(i<256 && res){
		res = (NodosIguales(n1->hojas[i], n2->hojas[i]));
		i++;
	}
	return res;	
}

template<typename T>
bool DiccionarioTrie<T>::NodosIguales(const Nodo* n1, const Nodo* n2)const{

	bool res = true;
	int i = 0;

	while(i<256 && res){
		res = (NodosIguales(n1->hojas[i], n2->hojas[i])) && (*(n1->significado) == *(n2->significado)) ;
		i++;
	}
	return res;
}
#endif
